package sort;

import utils.Util;

public class Sort {

    static void insertSort(int[] arr) {

        int i = 0;
        int j = 0;

        for (i = 1; i < arr.length; i++) {

            int target = arr[i];

            j = i - 1;
            while (j > -1 && arr[j] > target) {

                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = target;

        }

    }

    static void shellSort(int[] arr) {

        int i = 0;
        int j = 0;

        for (int interval = arr.length / 2; interval >= 1; interval /= 2) {

            for (i = interval; i < arr.length; i++) {

                int target = arr[i];

                j = i - interval;

                while (j > -1 && arr[j] > target) {
                    arr[j + interval] = arr[j];
                    j -= interval;
                }

                arr[j + interval] = target;

            }
        }

    }


    static void quicksort(int[] arr, int low, int high) {

        if (low >= high)
            return;

        int first = low;
        int last = high;
        int key = arr[first];

        while (first < last) {

            while (first < last && arr[last] >= key)
                --last;
            arr[first] = arr[last];

            while (first < last && arr[first] <= key)
                ++first;
            arr[last] = arr[first];
        }

        arr[first] = key;

        quicksort(arr, low, first - 1);
        quicksort(arr, first + 1, high);
    }

    static void Qsort(int a[], int low, int high) {
        if (low >= high) {
            return;
        }
        int first = low;
        int last = high;
        int key = a[first];/*用字表的第一个记录作为枢轴*/

        while (first < last) {
            while (first < last && a[last] >= key) {
                --last;
            }
            a[first] = a[last];/*将比第一个小的移到低端*/

            while (first < last && a[first] <= key) {
                ++first;
            }
            /*将比第一个大的移到高端*/
            a[last] = a[first];
        }
        a[first] = key;/*枢轴记录到位*/
        Qsort(a, low, first - 1);
        Qsort(a, first + 1, high);
    }

    static void quicksort2(int[] a, int start, int end) {

        if (start >= end)
            return;

        int low = start;
        int high = end;
        int key = a[low];

        while (low < high) {

            while (low < high && a[high] >= key)
                high--;
            a[low] = a[high];

            while (low < high && a[low] <= key)
                low++;
            a[high] = a[low];
        }

        a[low] = key;
        quicksort2(a, start, low - 1);
        quicksort2(a, low + 1, end);
    }

    public static void main(String[] args) {

        int[] a = new int[]{6, 1, 4, 9, 2, 0};
        quicksort2(a, 0, a.length - 1);
        Util.print(a);

    }
}
